#include <iostream>
using std::cout;
using std::endl;

struct Node {
  char ch;
  Node* next;
};

void Insert(Node** head, char ch) {
  Node* node = new Node;
  node->ch = ch;
  node->next = *head;
  *head = node;
}

void SlowFastPointer(Node* head) {
  Node* slow = head;
  Node* fast = head;
  while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
  }
  if (slow) cout << "slow:" << slow->ch << ", ";
  if (fast) cout << "fast:" << fast->ch << endl;
}

void Reverse(Node** head) {
  Node* p = *head;
  Node* p1 = nullptr;
  Node* p2 = nullptr;
  if (p) p1 = p->next;
  if (p1) p2 = p1->next;

  while (p && p1) {
    p1->next = p;
    p = p1;
    p1 = p2;
    if (p2) p2 = p2->next;
  }
  if (*head) (*head)->next = nullptr;
  *head = p;
}

// 反转前半部分（有点复杂，还得倒回来）。也可以前半部分头插方式插入新链表
bool ABAString(Node* head) {
  Node* slow = head;
  Node* slow1 = nullptr;
  Node* slow2 = nullptr;
  if (slow) slow1 = slow->next;
  if (slow1) slow2 = slow1->next;
  Node* fast = head;
  while (slow && slow1 && fast && fast->next) {
    fast = fast->next->next;
    slow1->next = slow;
    slow = slow1;
    slow1 = slow2;
    if (slow2) slow2 = slow2->next;
  }
  if (head) head->next = nullptr;

  Node* p = nullptr;
  Node* q = nullptr;
  if (fast) {
    // 奇数个
    p = slow->next;
    q = slow1;
  } else {
    // 偶数个
    if (slow) {
      p = slow->next;
      slow->next = slow1;
      q = slow;
    }
  }
  while (p && q) {
    if (p->ch != q->ch) return false;
    p = p->next;
    q = q->next;
  }
  return true;

  // TODO：倒回来前半部分
}

void Print(Node* head) {
  Node* p = head;
  while (p) {
    cout << p->ch;
    p = p->next;
  }
  cout << endl;
}

void testSlowFast() {
  Node* head = nullptr;
  Insert(&head, '1');
  Insert(&head, '2');
  Insert(&head, '3');
  Insert(&head, '4');
  Insert(&head, '5');
  Print(head);
  SlowFastPointer(head);
}

void testReverse() {
  Node* head = nullptr;
  Insert(&head, 'a');
  Insert(&head, 'b');
  Insert(&head, 'c');
  Insert(&head, 'd');
  Print(head);
  Reverse(&head);
  Print(head);
}

void testABAString() {
  Node* head = nullptr;
  Insert(&head, '1');
  Insert(&head, '2');
  Insert(&head, '3');
  Insert(&head, '2');
  Insert(&head, '1');
  Print(head);
  if (ABAString(head))
    cout << "Is abaString\n";
  else
    cout << "Not abaString\n";
}

int main() {
  // testSlowFast();
  // testReverse();
  testABAString();
}
